/* Travelling Salesman problem using the Dynamic Programming method
   Written by Chris Bodily and David Butler
   Modified for UNIX by Jeff Penfold
*/

#include <stdio.h>

#define NUM_CITIES          17
#define NUM_CITIES_MINUS_1  16
#define NUM_SUBSETS         65535   /* 2^(NUM_CITIES - 1) - 1 */

unsigned int table[NUM_CITIES_MINUS_1][NUM_SUBSETS+1];
unsigned int temp;
unsigned int min_distance;
unsigned int dist[NUM_CITIES][NUM_CITIES]={
{0, 863, 1077, 371, 338, 345, 738, 615, 726, 248, 552, 857, 485, 867, 753, 600, 891},
{863, 0, 558, 1234, 1047, 518, 1205, 338, 259, 1111, 311, 472, 952, 400, 286, 369, 1358},
{1077, 558, 0, 1448, 1261, 732, 647, 706, 817, 1325, 525, 948, 926, 958, 844, 477, 800},
{371, 1234, 1448, 0, 443, 716, 809, 896, 985, 327, 923, 962, 522, 972, 950, 971, 786},
{338, 1047, 1261, 443, 0, 529, 1076, 709, 798, 116, 736, 575, 823, 709, 763, 784, 1229},
{345, 518, 732, 716, 529, 0, 741, 612, 723, 593, 373, 854, 488, 864, 750, 255, 894},
{738, 1205, 647, 809, 1076, 741, 0, 1353, 1464, 960, 1114, 1595, 287, 1605, 1491, 836, 153},
{615, 338, 706, 896, 709, 612, 1353, 0, 111, 773, 239, 242, 1100, 252, 138, 517, 1506},
{726, 259, 817, 985, 798, 723, 1464, 111, 0, 862, 350, 223, 1211, 141, 35, 628, 1617},
{248, 1111, 1325, 327, 116, 593, 960, 773, 862, 0, 800, 639, 707, 773, 827, 848, 1113},
{552, 311, 525, 923, 736, 373, 1114, 239, 350, 800, 0, 481, 861, 491, 377, 278, 1267},
{857, 472, 948, 962, 575, 854, 1595, 242, 223, 639, 481, 0, 1342, 134, 188, 759, 1748},
{485, 952, 926, 522, 823, 488, 287, 1100, 1211, 707, 861, 1342, 0, 1352, 1238, 583, 406},
{867, 400, 958, 972, 709, 864, 1605, 252, 141, 773, 491, 134, 1352, 0, 114, 769, 1758},
{753, 286, 844, 950, 763, 750, 1491, 138, 35, 827, 377, 188, 1238, 114, 0, 655, 1644},
{600, 369, 477, 971, 784, 255, 836, 517, 628, 848, 278, 759, 583, 769, 655, 0, 989},
{891, 1358, 800, 786, 1229, 894, 153, 1506, 1617, 1113, 1267, 1748, 406, 1758, 1644, 989, 0}};


int main()
{
    register unsigned int j;
    register unsigned int x;
    register unsigned int y;
    register unsigned int z;

    /* fill in the zero set */
    for (x = 0; x < NUM_CITIES_MINUS_1; x++)
	table[x][0] = dist[x+1][0];

    /* now fill the 'table'  */
    for (x=1; x < NUM_SUBSETS; x++)
	for (y=0; y < NUM_CITIES_MINUS_1; y++)
	    if ( !( 1 & (x>>y) ) ) 
	    {
		min_distance = 0xFFFF;
		for (z = 0; z < NUM_CITIES_MINUS_1; z++)
		    if ( 1 & (x >> z) )
		    {
			j = x ^ (1 << z);
			temp = table[z][j] + dist[z+1][y+1];
			if (min_distance > temp)
			    min_distance = temp;
		    }
		table[y][x] = min_distance;
	    }

    /* now get the min distance */
    x = NUM_SUBSETS;
    min_distance = 0xFFFF;
    for (z = 0; z < NUM_CITIES_MINUS_1; z++)
    {
	j = x ^ (1 << z);
	temp = table[z][j] + dist[z+1][0];
	if (min_distance > temp)
	    min_distance = temp;
    }

    printf("Optimal Distance: %u\n", min_distance);

    return 0;
}

